package pl.agh.convexhulltutor.algorithms;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

import pl.agh.convexhulltutor.gui.DrawPanel;
import pl.agh.convexhulltutor.structures.Line;
import pl.agh.convexhulltutor.structures.Point;

public class QuickhullAlgorithm extends Algorithm {
	private Stack<QuickHullStepData> waitingSteps = new Stack<QuickHullStepData>();

	private boolean stepInProgress = false;

	public QuickhullAlgorithm(DrawPanel drawPanel) {
		super(drawPanel);
	}

	private void initialStep(List<Point> points, List<Line> lines) {
		Collections.sort(points);

		Line line = new Line(points.get(0), points.get(points.size() - 1));
		line.getPoint1().setColor(Point.CONVEX_HULL_COLOR);
		line.getPoint2().setColor(Point.CONVEX_HULL_COLOR);
		lines.add(line);

		QuickHullStepData leftSide = new QuickHullStepData(line);
		QuickHullStepData rightSide = new QuickHullStepData(line);
		for (Point point : points) {
			if (line.getPoint1().compareTo(point) != 0
					&& line.getPoint2().compareTo(point) != 0) {
				if (line.getDeterminantSign(point) > 0) {
					leftSide.addPoint(point);
				} else if (line.getDeterminantSign(point) < 0) {
					rightSide.addPoint(point);
				} else {
					point.setColor(Point.NON_CONVEX_HULL_COLOR);
				}
			}
		}
		if (!leftSide.getPoints().isEmpty()) {
			waitingSteps.add(leftSide);
		}
		if (!rightSide.getPoints().isEmpty()) {
			waitingSteps.add(rightSide);
		}
		if (leftSide.getPoints().isEmpty() || rightSide.getPoints().isEmpty()) {
			line.setColor(Line.CONVEX_HULL_COLOR);
		}
	}

	private void normalStep(List<Point> points, List<Line> lines) {
		if (!waitingSteps.isEmpty()) {
			QuickHullStepData stepData;
			if (stepInProgress == false) {
				stepData = waitingSteps.peek();
			} else {
				stepData = waitingSteps.pop();
			}
			stepData.updatePoints(points);

			Point mostDistantPoint = stepData.getMostDistantPoint();
			if (mostDistantPoint != null) {
				Point point1 = stepData.line.getPoint1();
				Point point2 = stepData.line.getPoint2();

				if (stepInProgress == false) {
					mostDistantPoint.setColor(Point.CONVEX_HULL_COLOR);
					lines.add(new Line(mostDistantPoint, point1));
					lines.add(new Line(mostDistantPoint, point2));
				} else {
					if (getDeterminantSign(point1, point2, mostDistantPoint) < 0) {
						Point tmp = point1;
						point1 = point2;
						point2 = tmp;
					}
					QuickHullStepData rightSide1 = new QuickHullStepData(
							new Line(point2, mostDistantPoint));
					QuickHullStepData rightSide2 = new QuickHullStepData(
							new Line(mostDistantPoint, point1));
					for (Point point : stepData.getPoints()) {
						if (isPointInsideTriangle(point, point1, point2,
								mostDistantPoint)) {
							point.setColor(Point.NON_CONVEX_HULL_COLOR);
						} else if (getDeterminantSign(point2, mostDistantPoint,
								point) < 0) {
							rightSide1.addPoint(point);
						} else if (getDeterminantSign(point2, mostDistantPoint,
								point) > 0) {
							rightSide2.addPoint(point);
						}
					}
					if (!rightSide1.getPoints().isEmpty()) {
						waitingSteps.add(rightSide1);
					} else {
						lines.get(lines.size() - 2).setColor(
								Line.CONVEX_HULL_COLOR);
					}
					if (!rightSide2.getPoints().isEmpty()) {
						waitingSteps.add(rightSide2);
					} else {
						lines.get(lines.size() - 1).setColor(
								Line.CONVEX_HULL_COLOR);
					}
				}
			}

			stepInProgress = stepInProgress == true ? false : true;
		}
	}

	@Override
	public void execute(List<Point> points, List<Line> lines) {
		if (currentStep == 1) {
			initialStep(points, lines);
		} else {
			normalStep(points, lines);
		}
		if (waitingSteps.isEmpty()) {
			List<Line> newLines = new ArrayList<Line>();
			for (Line line : lines) {
				if (line.getColor() == Line.CONVEX_HULL_COLOR) {
					newLines.add(line);
				}
			}
			lines.clear();
			lines.addAll(newLines);
			maxStep = currentStep;
		}
	}

	private class QuickHullStepData {
		private Line line;
		private List<Point> stepPoints = new ArrayList<Point>();

		public QuickHullStepData(Line line) {
			this.line = line;
		}

		public void addPoint(Point point) {
			stepPoints.add(point);
		}

		public void updatePoints(List<Point> currentPoints) {
			for (int i = 0; i < stepPoints.size(); i++) {
				for (int j = 0; j < currentPoints.size(); j++) {
					if (stepPoints.get(i).isIdentical(currentPoints.get(j))) {
						stepPoints.set(i, currentPoints.get(j));
						break;
					}
				}
			}
		}

		public List<Point> getPoints() {
			return stepPoints;
		}

		public Point getMostDistantPoint() {
			Point mostDistantPoint = null;
			for (Point point : stepPoints) {
				if (mostDistantPoint == null
						|| line.getDistanceToPoint(point) > line
								.getDistanceToPoint(mostDistantPoint)) {
					mostDistantPoint = point;
				}
			}
			return mostDistantPoint;
		}
	}
}
